This book is not complete. You may not want to take a link to this page, as the url may change.
Table of contents
- The simplest interpreter
The simplest interpreter
print("First number: ")
a = read_number()
print("Second number: ")
b = read_number()
c = a + b
print("Result: ", c)
Despite it looking simple, it gives us the possibility to talk about many things.
Text, memory and representing expressions
Try to ignore for a moment that the input method of this interpreter – typing numbers in the terminal – isn't great. One thing that is great is the way that the input is stored in memory. The program is composed of two numbers, so we store each number in a separate variable.
A way worse representation would be, for example, a single variable containing the string "12 + 25". A slightly better, but still not great, representation would be two variables, one containing the string "12", the other containing the string "25".
Why? Because adding the string representation of two numbers isn't as easy as directly adding the numbers. You would need to either convert the strings to numbers and then add them, or have a special algorithm to add strings containing numbers.
Even worse, if you had a single string, you would first need to figure out what are the substrings containing the numbers, then proceed as above. In other words, you would need to parse the input program.
Imagine that we want to improve our interpreter to now allow not only addition, but also subtraction and multiplication (let's ignore division for now). If we try to keep the same focus as before (make the in-memory representation easy to work with, and don't care about the input method), the most obvious thing to do is to add another variable:
...
print("The operation: ")
o = read_operator()
/* compute c based on a, b and o */
...
The computation would then look something like this:
switch o case +: c = a + b case -: c = a - b case *: c = a * b
Super easy, barely an inconvenience.
Let's make our interpreter do more work. Let's have it take an arbitrary amount of numbers and combine them with arbitrary operations. We want to compute an expression like 12 + 25 - 7 * 2 + 34. Still thinking about how to represent things in memory to make computation easier, the natural extension of our current interpreter is a pair of arrays:
numbers: [N]Number operators: [N-1]Operator
After the arrays are filled, it's just a simple loop to finally compute the result:
c = numbers[0] for i = 1; i < N; i += 1 a = c b = numbers[i] o = operators[i - 1] /* compute c based on a, b and o */
Then print the result. For our example expression, this prints 94. That's great!
But wait, the result is wrong. The actual result is 57, not 94. What happened?
The problem is that if you do that by hand, the first operation you would do is 7 * 2 (because the convention we humans agreed on is to do multiplication before addition and subtraction). That's called operator precedence. If you try to input that expression in a real programming language, you would get 57. But our interpreter doesn't know about operator precedence – operators are stored in a linear collection, without any way to model their relationship.
There are two ways to proceed:
the first: keep a linear data structure, but reorder the numbers and operators as you read them so that walking the array linearly will produce the collect result;
the second: trash the linear data structure, and store the input program in a way that models the order of operations.
In other words:
the first: keep the array;
the second: ditch the array and use a tree.
Both ways are possible, and I will explain both of them. Later.
However, I will now give you a bit of a spoiler into where and when each representation is used. Without it, this book will have to contain duplicate sections for every part related to interpreting expressions. Not only it would be a waste of time for me to write, but it would be a waste of time for you to read, and a waste of digital space.
Instead, I will now simply choose one way that I'll use for the rest of the book, and then tell you what would need to change if you ever wanted to try the other approach.
The spoiler is the following: Usually a programming language isn't made of just expressions, but of other things too. These other things are better modeled with trees. To keep some internal consistency between the various parts of the interpreter, we will use trees for expressions too. If you want to write this part of the interpreter with a linear data structure, you can consider this your "exercise for the reader".
Both of these methods are "solved" problems. However, I would like you to think about something: just because parsing a language is easy, it doesn't mean that text is the best way to store and share source code. This is one of the reasons why this book does not start with parsing: you need to know that an interpreter isn't its parser. The interesting and important parts of interpreting a program come after the parsing, as the parser is simply a way to get source code from text into a form that is easy to work with. You need to understand what are the problems caused by storing things as text, and how much better it would be if code was stored in a different format. This book will not provide a solution to the problem of code stored as text. That is way out of scope, and possibly the subject of research for the years to come. Who knows, after you finish reading this book, you may want to give it a shot and free us from the constrictions of text.
Expression trees
So, as we agreed, we skip parsing for now and imagine that the source code is simply handed to us in the right format. And, as we agreed (if you trust me) the "right" format for an expression is a tree.
What kind of tree? Binary? N-ary?
All the expression in our examples so far can be composed by two kinds of nodes: the literal and the binary expression.
In programming languages, literals are values that are written directly in the source code. For example: 12. In the expression 12 + 25, '12' and '25' are literals. Each literal could be its own individual expression without any children.
Binary expressions are anything that has two sub-expressions and an operator that combines them. '12 + 25' is a binary expression. '+' is the root of the expression tree, and '12' and '25' are its sub-expressions.
We can model this directly in the code by allowing an expression to be either a Literal or a Binary_Expression.
Expression :: union {
Literal, // Not defined yet
Binary_Expression, // Not defined yet
}
(NOTE: If you like inheritance, fat structs or other forms of abstraction, the union is simply the most obvious way to explain and understand this concept. If, after you wrote the code this way, you think you can improve it then go ahead. But for the remainder of the book, I'll stick with union, and you should too if you want to follow along. Remember that code can change.)
We can then define its variants:
Literal :: struct {
value: Number
}
Binary_Expression :: struct {
operator: Operator,
sub_1: ^Expression,
sub_2: ^Expression
}
We can now represent literals and binary expressions. We don't yet have a way to generate instances of expressions, but we can hard-code some examples in the interprete to test things out:
main :: () {
a: Expression = Literal { 12 }
b: Expression = Literal { 25 }
root: Expression = Binary_Expression { +, &a, &b }
c: Number = eval_expression(root)
print(c)
}
How do we evaluate an expression? Depends on the kind. The evaluation function just switches on the variant and picks the appropriate evaluation method.
eval_expression :: (ast: Expression) -> Number {
result: Number
switch type_of(ast) {
case Literal: result = eval_literal(ast) // Not defined yet
case Binary_Expression: result = eval_binary_expression(ast) // Not defined yet
}
return result
}
NOTE: I made separate functions for each variant of the expression so that the snippet is more digestible inside a book. In a real codebase, you might want to inline them and have eval_expression be your only function. I would probabily do that if I weren't writing a book, but this is a book.
Evaluating a literal is as simple as returning its value:
eval_literal :: (ast: Literal) -> Number {
return ast.value
}
The binary expression is slightly more involved, but nothing we can't handle. We just need to compute the result differently based on the operator:
eval_binary_expression :: (ast: Binary_Expression) -> Number {
a := eval_expression(ast.sub_1)
b := eval_expression(ast.sub_2)
result: Number
switch ast.operator {
case +: result = a + b
case -: result = a - b
case *: result = a * b
}
return result
}
We can now run the interpreter and see the result! If you run it now, with the 'main' defined as above, it should correctly print 37.
Division and errors
There is one binary operator that we voluntarily left out: the division. Division requires special handling because it is not mathematically defined if the divisor is 0. This is the perfect opportunity to talk a bit about language design and error handling.
If you divide a number by zero in your implementation language, what happens? Each language is different, and it may have different answers depending on the data type of your numbers and other factors. If your language has floating-point numbers, and you're doing floating-point division, dividing by zero yields infinity (check).
If you're doing integer division, then the language might panic, yield 0, yield 1, yield a special sentinel value or something completely different like invoke undefined behaviour.
What should your interpreter do? This is your opportunity to wear your language designer hat and take a decision. There is simply no "right" answer, there is only your answer. Sure, some choices are saner than others, but it's ultimately you who decides. Keep in mind that, whatever you choose, your users will have to remember that choice when they write divisions.
Let's say you want it to return infinity:
switch ast.operator {
...
case /:
if b != 0 result = a / b
else result = math.sign(a) * math.INFINITY
}
Let's try something else: we want to instead panic the program. In other words, we want to genrate a runtime error.
Read that carefully: we want to panic the program that is being interpreted, not the interpreter itself. Those are two very different things. A panic/assert that fires in a program indicates that the program has a bug. Whenever you write code in general, you want to eliminate as many bugs as possible. We don't want the interpreter to have bugs, but we do want to account for the possibility of a bug in the interpreted code.
This is different than, say, handling the case where the operator isn't any of the four cases that we expect. If 'operator' isn't any of +, -, * or /, then that's a bug in the interpreter. It means that whoever gave us the expression tree (the parser) gave us an incorrect tree, which should not have happened. In THAT case, we do want to stop the interpreter:
switch ast.operator {
case +: ...
case -: ...
case *: ...
case /: ...
case: internal_error("Invalid operator.")
}
(or, first introduce errors in the interpreter, then errors in the target language. explain why you don't like to call errors 'errors'. Differentiate between asserts, internal_error() and returning a status code. Let's say you want to call the interpreter from a graphical, interactive program: you don't want to trap, but just abort interpretation. A case like this is not an assert, but a runtime_error() which sets a flag in the interpreter.)
eval_binary_expression :: (ast: Binary_Expression) -> Number, Error {
result, error: Number, Error
...
case /:
if b != 0 result = a / b
else result, error = 0, Error { "Division by zero." }
...
return result, error
}
Wait, but then we would need to update eval_expression to also aknowledge the possibility of errors:
eval_expression :: (ast: Expression) -> Number, Error {
result, error: Result, Error
switch type_of(ast) {
case Literal: result = eval_literal(ast)
case Binary_Expression: result, error = eval_binary_expression(ast)
case: internal_error("Invalid expression variant.")
}
return result, error
}
Wait, but then eval_binary_expression needs to account for the possibility of either of its sub-expressions returning errors.
eval_binary_expression :: (ast: Binary_Expression) -> Number, Error {
result, error: Number, Error
a, error_a := eval_expression(ast.sub_1)
b, error_b := eval_expression(ast.sub_2)
if error_a == nil and error_b == nil {
switch ast.operator {
...
}
} else {
error = error_a
}
return result, error
}
Now you might think, if you like exceptions, this might be a good time to use exceptions. (explain simple control flow. This code is not complicated at all, exceptions aren't worth it. Use them if you really want, but look at the example code and see if it all that bad without them.)